package datastruct.linkedlist.skiplist;

import java.util.Random;

/**
 * 参考
 * https://blog.csdn.net/weixin_41622183/article/details/91126155
 * @author Yankj
 *
 */
public class SkipListDemo {

}

class SkipList<T>{

	/**
	 * 跳跃表的节点
	 * @author Yankj
	 *
	 * @param <T>
	 */
	private static class SkipNode<E> {
		
		/**
		 * 存储的数据
		 */
		E val;
		
		/**
		 * 跳跃表按照这个分数值进行从小到大排序
		 */
		Integer score;
		
		/**
		 * next指针
		 */
		SkipNode<E> next;
		
		/**
		 * 指向下一次层的指针
		 */
		SkipNode<E> down;
		
		public SkipNode(E val, int score) {
			this.val = val;
			this.score = score;
		}
		
	}
	
	/** 节点的高度，这里限制最高 4 层 */
	private static final int MAX_LEVEL = 4;
	
	/**
	 * 跳跃表数据结构
	 */
	private SkipNode<T> head;
	
	/**
	 * 节点级别
	 */
	private int level = 0;
	
	/**
	 * 用于产生随机数的Random对象
	 **/
	private Random random = new Random();
	
	public SkipList() {
		//创建默认初始高度的跳跃表
		this(MAX_LEVEL);
	}
	
	public SkipList(int level) {
		this.level = level;
		int i = level;
		SkipNode<T> temp = null;
		SkipNode<T> pre = null;
		
		while (i-- != 0) {
			temp = new SkipNode<T>(null, Integer.MAX_VALUE);
			temp.down = pre;
			pre = temp;
		}
		// 头节点 
		head = temp;
	}
	
	/**
	 * 产生节点的高度。使用抛硬币
	 * @return
	 */
	private int getRandomLevel() {
		int lev = 1;
		while (random.nextInt() % 2 == 0) {
			lev++;
		}
		
		return lev>MAX_LEVEL?MAX_LEVEL:lev;
	}
	
	/**
	 * 查找跳跃表中的一个值
	 * @param score
	 * @return
	 */
	public T get(Integer score) {
		SkipNode<T> t = head;
		while(t != null) {
			if(t.score.equals(score)) {
				return t.val;
			}
			
			if(t.next == null || score < t.next.score) {
				t = t.down;
			}else if(score >= t.next.score) {
				t = t.next;
			}
			
		}
		return t != null ? t.val : null;
	}
	
	
}